/*
 * @lc app=leetcode.cn id=1824 lang=golang
 *
 * [1824] 最少侧跳次数
 */
package Solutions

// @lc code=start
func minSideJumps(obstacles []int) int {
	var dp = make([][3]int, len(obstacles))
	dp[0][0] = 1
	dp[0][2] = 1
	for i := 1; i < len(obstacles); i++ {
		obstacles[i] -= 1
		minI := -1
		for j := 0; j < 3; j++ {
			if obstacles[i] == j {
				continue
			}
			if minI == -1 {
				minI = j
			}
			if dp[i-1][minI] > dp[i-1][j] {
				minI = j
			}
		}
		dp[i][minI] = dp[i-1][minI]
		if obstacles[i] >= 0 {
			dp[i][obstacles[i]] = 1<<31 - 1
		}

		for j := 0; j < 3; j++ {
			if j == obstacles[i] || j == minI {
				continue
			}
			dp[i][j] = min_nn(dp[i-1][minI]+1, dp[i-1][j])
		}

	}
	ansI := 0
	if dp[len(dp)-1][1] < dp[len(dp)-1][ansI] {
		ansI = 1
	}
	if dp[len(dp)-1][2] < dp[len(dp)-1][ansI] {
		ansI = 2
	}
	return dp[len(dp)-1][ansI]
}

func min_nn(i, j int) int {
	if i < j {
		return i
	}
	return j
}

// @lc code=end
